package com.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author Jinpeng Lin
 * @description 763. 划分字母区间：https://leetcode-cn.com/problems/partition-labels/
 * @date 2021-10-29
 */
public class Leetcode763 {

    /**
     * 解题思路：
     * 分析：
     * 1. 每个片段中字母不可以重复，因此我需要知道单个片段中，每个字母的最后位置，然后找到其中索引位置最远的那个，这个位置为片段尾
     * 2. 为了知道每个字母的最后位置，递归一次字母，将每个字母的最后索引存到 HashMap，方便后面查找判断
     * 3. 外层循环为片段，内存循环用来更新最后位置
     * 4. 以片段头为开始位置，预设置的片段尾（第一个字母的最远索引位置）为结束位置，判断范围内字母的最远位置是否存在超过已有的最远位置，存在更新最远位置
     * 5. 片段结束后将片段的开始与结束位置初始化为下个片段的开始位置，进入循环后对结束位置再次进行预设值
     * 6. 外层循环如何结束？假如最后一个片段循环结束，此时 last + 1 == arr.length，退出循环
     * @return
     */
    public static List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();
        HashMap<Character, Integer> map = new HashMap<>(16);
        char[] arr = s.toCharArray();
        // 递归，记录下每个字母的最远下标
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], i);
        }
        // 开始位置
        int start = 0;
        // 结束位置
        int last = 0;
        // 外层循环为片段
        for (int i = 0; i < arr.length; i = last) {
            // 获取当前字母的最远位置
            last = map.get(arr[i]);
            // 内层循环更新最远位置 last，如果发现范围内字母的最远位置超过当前最远位置，更新最远位置
            for (int j = 0; j < last; j++) {
                if (map.get(arr[j]) > last) {
                    last = map.get(arr[j]);
                }
            }
            // 记录下片段长度
            //  0  1  2  3
            // [a, b, a, c] = a,b,a = 2 - 0 + 1 = 3
            // [a, b, a, c] =   c   = 3 - 3 + 1 = 1
            result.add(last - start + 1);
            // 记录下已经处理过的位置，从之后位置继续
            start = ++last;
        }
        return result;
    }

    public static void main(String[] args) {
        String s = "ababcbacadefegdehijhklij";
        System.out.println(partitionLabels(s));
    }
}
